Search for: All records

We consider a minimization variant on the classical prophet inequality with monomial cost functions. A firm would like to procure some fixed amount of a divisible commodity from sellers that arrive sequentially. Whenever a seller arrives, the seller’s cost function is revealed, and the firm chooses how much of the commodity to buy. We first show that if one restricts the set of distributions for the coefficients to a family of natural distributions that include, for example, the uniform and truncated normal distributions, then there is a thresholding policy that is asymptotically optimal in the number of sellers. We then compare two scenarios based on whether the firm has in-house production capabilities or not. We precisely compute the optimal algorithm’s competitive ratio when in-house production capabilities exist and for a special case when they do not. We show that the main advantage of the ability to produce the commodity in house is that it shields the firm from price spikes in worst-case scenarios. Funding: This work was supported by NSF Grants [CNS-2146814, CPS-2136197, CNS-2106403, NGSDI-2105648]. 

We study a generalization of the secretary problem, where decisions do not have to be made immediately upon applicants’ arrivals. After arriving, each applicant stays in the system for some (random) amount of time and then leaves, whereupon the algorithm has to decide irrevocably whether to select this applicant or not. The arrival and waiting times are drawn from known distributions, and the decision maker’s goal is to maximize the probability of selecting the best applicant overall. Our first main result is a characterization of the optimal policy for this setting. We show that when deciding whether to select an applicant, it suffices to know only the time and the number of applicants that have arrived so far. Furthermore, the policy is monotone nondecreasing in the number of applicants seen so far, and, under certain natural conditions, monotone nonincreasing in time. Our second main result is that when the number of applicants is large, a single threshold policy is almost optimal. Funding: A. Psomas is supported in part by the National Science Foundation [Grant CCF-2144208], a Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2476 . 

A single homogeneous resource needs to be fairly shared between users that dynamically arrive and depart over time. Although good allocations exist for any fixed number of users, implementing these allocations dynamically is impractical: it typically entails adjustments in the allocation of every user in the system whenever a new user arrives. We introduce a dynamic fair resource division problem in which there is a limit on the number of users that can be disrupted when a new user arrives and study the trade-off between fairness and the number of allowed disruptions, using a fairness metric: the fairness ratio. We almost completely characterize this trade-off and give an algorithm for obtaining the optimal fairness for any number of allowed disruptions. 

This paper presents a black-box framework for accelerating packing optimization solvers. Our method applies to packing linear programming problems and a family of convex programming problems with linear constraints. The framework is designed for high-dimensional problems, for which the number of variables n is much larger than the number of measurements m. Given an [Formula: see text] problem, we construct a smaller [Formula: see text] problem, whose solution we use to find an approximation to the optimal solution. Our framework can accelerate both exact and approximate solvers. If the solver being accelerated produces an α-approximation, then we produce a [Formula: see text]-approximation of the optimal solution to the original problem. We present worst-case guarantees on run time and empirically demonstrate speedups of two orders of magnitude.